package consistenthhash

import (
	"hash/crc32"
	"sort"
	"strconv"
)

type Hash func(data []byte) uint32

// 一致性hash算法的主数据结构
type Map struct {
	hash Hash
	// 虚拟节点倍数
	replicas int
	// 哈希环
	keys []int
	// 虚拟节点和真实节点的映射表
	hashMap map[int]string
}

func New(replicas int, fn Hash) *Map {
	m := &Map{
		replicas: replicas,
		hash: fn,
		hashMap: make(map[int]string),
	}

	if m.hash == nil {

		//返回数据data使用IEEE多项式计算出的CRC-32校验和
		m.hash = crc32.ChecksumIEEE
	}
	return m
}
// 传入多个节点名称
func (m *Map) Add(Keys ...string) {
	for _, key := range Keys {
		for i := 0; i < m.replicas; i++ {
			// 根据指定的倍数创建对应数量的虚拟节点
			hash := int(m.hash([]byte(strconv.Itoa(i) + key)))
			// 把虚拟节点添加到哈希环中。
			m.keys = append(m.keys, hash)
			// 映射 虚拟节点对应的真实节点
			m.hashMap[hash] = key
		}
	}
	// 环上的 hash 排序
	// 快排算法
	sort.Ints(m.keys)
}
// 选择节点

func (m *Map) Get(key string) string {
	if len(m.keys) == 0 {
		return ""

	}
	// 获取对应的 节点的hash 值
	hash := int(m.hash([]byte(key)))
	// 顺时针找到第一个匹配的虚拟节点的下标
	idx := sort.Search(len(m.keys), func(i int) bool {
		// m.keys存储的为虚拟节点的 hash值
		// 找到第一个 对应的 hash
		return m.keys[i] >= hash

	})
	// 返回对应的 真实节点
	// 因为是 环状结构 idx == len(m.keys) 需要 取余操作
	return  m.hashMap[m.keys[idx % len(m.keys)]]


}